package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/** @author haoyang.shi */
public class VerifySquenceOfBST {

  @Test
  public void test() {
    System.out.println(VerifySquenceOfBST(new int[] {1, 3, 5, 7, 6, 4}));
    System.out.println(VerifySquenceOfBST(new int[] {3, 2, 5, 7, 6, 4}));
    System.out.println(VerifySquenceOfBST(new int[] {10, 3, 9, 5, 7, 6, 4}));
  }

  public boolean VerifySquenceOfBST(int[] sequence) {
    if (sequence.length == 0) {
      return false;
    }

    if (sequence.length == 1) {
      return true;
    }

    return isBST(sequence, 0, sequence.length - 1);
  }

  private boolean isBST(int[] sequence, int start, int end) {
    if (start < 0 || end < 0 || start >= end) {
      return true;
    }

    int rootV = sequence[end];
    int rightIndex = -1, rightV = Integer.MIN_VALUE;
    for (int i = start; i < end; i++) {
      if (rightV == Integer.MIN_VALUE && sequence[i] > rootV) {
        rightV = sequence[i];
        rightIndex = i;
        continue;
      }

      if (rightV != Integer.MIN_VALUE && sequence[i] < rootV) {
        return false;
      }
    }

    return isBST(sequence, start, rightIndex - 1) && isBST(sequence, rightIndex, end - 1);
  }
}
